(* SML sets -- from Denmark Technical University *)

signature SET = sig
   type ''a set

   val empty : ''a set
   val null : ''a set -> bool
   val singleton : ''a -> ''a set
   val member : ''a * ''a set -> bool
   val insert : ''a * ''a set -> ''a set
   val union : ''a set * ''a set -> ''a set
   val unionOver : ''a set -> (''a -> ''b set) -> ''b set
   val inter : ''a set * ''a set -> ''a set
   val diff :  ''a set * ''a set -> ''a set
   val delete : ''a set * ''a -> ''a set
   val subset : ''a set * ''a set -> bool
   val equal : ''a set * ''a set -> bool
   val fromList : ''a list -> ''a set
   val toList : ''a set -> ''a list
   val card : ''a set -> int
   val filter : (''a -> bool) -> ''a set -> ''a set
   val exists : (''a -> bool) -> ''a set -> bool
   val all : (''a -> bool) -> ''a set -> bool
   val find : (''a -> bool) -> ''a set -> ''a option
   val map : (''a -> ''b) -> ''a set -> ''b set
   val mapPartial : (''a -> ''b option) -> ''a set -> ''b set
   val app : (''a -> unit) -> ''a set -> unit
   val fold : (''a * 'b -> 'b) -> 'b -> ''a set -> 'b
   val choose : ''a set -> ''a
end

structure Set : SET = struct
   type ''a set = ''a list  (* [a1,...,an] with ai <> aj for i <> j *)

   val empty = []
   fun null [] = true
     | null _  = false

   fun member (x, ys) = List.exists (fn y => x=y) ys;
   fun insert (x, ys) = if member(x,ys) then ys else x::ys

   fun union (xs, ys) = List.foldl insert ys xs
   fun unionOver s m = List.foldl union empty (List.map m s)
   fun inter (xs, ys) = List.filter (fn x => member(x, ys)) xs
   fun diff  (xs, ys) = List.filter (fn x => not (member(x, ys))) xs
   fun delete ([], _)    = []
     | delete (x::xs, y) = if x=y then xs else x::delete(xs,y)

   fun subset (xs, ys) = List.all (fn x => member(x, ys)) xs;
   fun equal (xs, ys) = subset(xs, ys) andalso subset(ys, xs);

   fun fromList xs = List.foldl insert empty xs
   fun toList xs = xs

   fun card xs = List.length xs
 
   fun filter p xs = List.filter p xs

   fun exists p xs = List.exists p xs

   fun all p xs = List.all p xs

   fun find p xs = List.find p xs

   fun map f s = List.foldl (fn (y,ys) => insert(f y, ys)) empty s
   fun mapPartial f s = List.foldl (fn (y,ys) => 
				       let val v = f y
				       in case v of
					      SOME v' => insert(v', ys)
					    | NONE => ys
				       end)
				   empty s
   fun app f s = List.app f s

   fun fold f = List.foldl f

   fun singleton a = insert (a, empty)

   fun choose xs = hd xs

end;
